package pl.edu.agh.gronoMining.frequentSubgraphFinder.frequentSearcher;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.apache.log4j.Logger;

import pl.edu.agh.gronoMining.frequentSubgraphFinder.frequentSearcher.subgraph.DFSCode;
import pl.edu.agh.gronoMining.frequentSubgraphFinder.frequentSearcher.subgraph.StartNodeSubgraph;
import pl.edu.agh.gronoMining.frequentSubgraphFinder.frequentSearcher.subgraph.StartNodeSubgraphList;
import pl.edu.agh.gronoMining.frequentSubgraphFinder.frequentSearcher.subgraph.SubgraphMove;
import pl.edu.agh.gronoMining.frequentSubgraphFinder.frequentSearcher.subgraph.impl.StartNodeSubgraphImpl;
import pl.edu.agh.gronoMining.frequentSubgraphFinder.frequentSearcher.subgraph.impl.StartNodeSubgraphListImpl;
import pl.edu.agh.gronoMining.frequentSubgraphFinder.graph.Graph;
import pl.edu.agh.gronoMining.frequentSubgraphFinder.graph.GraphException;
import pl.edu.agh.gronoMining.frequentSubgraphFinder.graph.Node;
import pl.edu.agh.gronoMining.frequentSubgraphFinder.strategy.Strategy;

/**
 * Perform frequent subgraph mining
 */
public class FrequentGraphsMiner {

	private Graph inputGraph;
	private Strategy strategy;
	private int minimumFrequency;
	private boolean isTree;
	
	private static Logger logger = Logger.getLogger(FrequentGraphsMiner.class);
	
	/**
	 * @param inputGraph input graph
	 * @param strategy strategy object
	 * @param minimumFrequency minimum number of subgraph to be frequent
	 * @param isTree is graph a tree
	 */
	public FrequentGraphsMiner(Graph inputGraph, Strategy strategy, int minimumFrequency, boolean isTree) {
		this.inputGraph = inputGraph;
		this.strategy = strategy;
		this.minimumFrequency = minimumFrequency;
		this.isTree = isTree;
	}
	
	/**
	 * Perform frequent subgraph mining
	 * @return set of frequent subgraphs
	 * @throws GraphException
	 */
	public Set<Graph> startMining() throws GraphException {
		
			// create StartNodeSubgraphList and result set
		StartNodeSubgraphList startNodeList = new StartNodeSubgraphListImpl();
		Set<DFSCode> resultDfsSet = new HashSet<DFSCode>();
		
			// create StartNodeSubgraph object for every start node and add it to startNodeList
		for (Node node : inputGraph.getAllNodes()) {
			if (node.getType() == strategy.getStartType()) {
				StartNodeSubgraph sns = new StartNodeSubgraphImpl(node, this.strategy);
				startNodeList.addStartNodeSubgraph(sns);
			}
		}
		
			// while size of startNodeList >= minimumFrequency take first StartNodeSubgraph, call performMining
			// and remove this startNodeSubgraph
		try {
			while (startNodeList.size() >= minimumFrequency) {
				StartNodeSubgraph subgraph = startNodeList.getFirstStartNodeSubgraph();
				subgraph.markAsActive();
				this.performMining(subgraph, startNodeList, resultDfsSet, this.minimumFrequency, null, this.isTree);
				startNodeList.remove(subgraph);
				logger.info(" ====  end mining this subgraph ==== ");
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
		
			// create result set using resultDfsSet
		Set<Graph> resultSet = new HashSet<Graph>();
		for (DFSCode dfs : resultDfsSet)
			resultSet.add(dfs.getAsGraph());
		
		return resultSet;
	}
	
	/**
	 * @param subgraph active startNodeSubgraph
	 * @param startNodeList current startNodeList
	 * @param resultDfsSet result set
	 * @param minimumFrequency
	 * @param dfs dfs of current active startNodeSubgraph
	 * @param isTree is input graph a tree
	 * @throws GraphException
	 */
	private void performMining(StartNodeSubgraph subgraph, StartNodeSubgraphList startNodeList, Set<DFSCode> resultDfsSet, int minimumFrequency, DFSCode dfs, boolean isTree) throws GraphException {
		
			// if there is no current active startNodeSubgraph - create one
		if (dfs == null)
			dfs = subgraph.getAsDfs();
		
			// generate possible moves of active startNodeSubgraph
		List<SubgraphMove> moves = subgraph.getPossibleMoves(dfs, resultDfsSet);
		
			// for every generated move...
		for (SubgraphMove move : moves) {
		
			//TODO: what if this edge was checked before
				
				// try to perform move in every startNodeSubgraph from startNodeList. Generate new StartNodeSubgraphList
				// of startNodeSubgraphs which this move was performed successfully
			//logger.info("check move - "+move);
			StartNodeSubgraphList subgraphsWhichMoveSucceed = startNodeList.performMove(move);
			//logger.info("move is possible in "+subgraphsWhichMoveSucceed.size()+" graphs");
			
				// checks if move was successful in more than 'minimumFrequency' graphs
			if (subgraphsWhichMoveSucceed.size() >= minimumFrequency) {
					
					// generate new dfs of active startNodeSubgraph (after move)
				DFSCode newDfs = subgraph.getAsDfs();
				
					// save generated dfs to result set
				//logger.info(" == save to result set == "+newDfs.getId1Array().length);
				resultDfsSet.add(newDfs);
				
					// mark edge of this move as frequent
				if (shouldMarkDfs(dfs, subgraphsWhichMoveSucceed.size(), true)) {
					if (move.isCreatingPath() && isTree)
						subgraphsWhichMoveSucceed.markLastMoveEdge(true);
					else
						subgraphsWhichMoveSucceed.markLastMoveEdge(true, dfs);
				}
				
					// call this function but use startNodeSubgraphList of subgraphs that successfully performed move
				//logger.info("call performMining");
				this.performMining(subgraph, subgraphsWhichMoveSucceed, resultDfsSet, minimumFrequency, newDfs, isTree);
				//logger.info("return from performMining");
				
			} else {
					// if move wasn't successful mark edge of this move as unfrequent
				if (shouldMarkDfs(dfs, subgraphsWhichMoveSucceed.size(), false)) {
					if (move.isCreatingPath() && isTree)
						subgraphsWhichMoveSucceed.markLastMoveEdge(false);
					else
						subgraphsWhichMoveSucceed.markLastMoveEdge(false, dfs);
				}
			}
				// in every startNodeSubgraph from startNodeList undo last move
			//logger.info("undo last move");
			subgraphsWhichMoveSucceed.undoLastMove();
		}		
	}
	
	/**
	 * function that decides if dfs should be saved in memoru or not
	 * @param dfs dfs to save
	 * @param number number of subgraphs that contains this dfs 
	 * @return true to save this dfs
	 */
	private boolean shouldMarkDfs(DFSCode dfs, int number, boolean isFrequent) {
		//return false;
		//if (isFrequent == true)
		//return false;
		
		//if (dfs == null && isFrequent)
		if (isFrequent)
			return false;
		return true;
	}
		
}
